
//根据一棵树的前序遍历与中序遍历构造二叉树。

//树节点接口定义
interface TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
}
class TreeNode {
    val: number;
    constructor(value: number) {
        this.val = value;
    }
}
// 暴露接口
var buildTree: (preorder: number[], inorder: number[]) => TreeNode | null = function (preorder, inorder) {
    // 递归出口
    if (inorder.length < 1) {
        return null;
    }
    // 确定当前子数根节点,索引
    let root: TreeNode = new TreeNode(preorder[0]);
    // 确定根节点在中序遍历的位置
    let rootIndex: number = inorder.indexOf(preorder[0]);
    // 确定左子树元素个数
    let leftTreeCount: number = rootIndex;
    // 递归的构造左子树
    root.left = buildTree(preorder.slice(1, 1 + leftTreeCount), 
    inorder.slice(0, rootIndex));
    // 递归的构造右子树
    root.right = buildTree(preorder.slice(1 + leftTreeCount, preorder.length), 
    inorder.slice(rootIndex + 1, inorder.length));
    return root;
};

        // 在「递归」地遍历某个子树的过程中，我们也是将这颗子树看成一颗全新的树，按照上述的顺序进行遍历。
        // 挖掘「前序遍历」和「中序遍历」的性质，我们就可以得出本题的做法。
        // 对于任意一颗树而言，前序遍历的形式总是根节点->左子树的前序遍历结果->右子树的前序遍历结果
        // 即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是->左子树的中序遍历结果->根节点->右子树的中序遍历结果
        // 只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。
        // 由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，
        // 因此我们就可以对应到前序遍历的结果中，对上述的所有左右子树进行定位。
        // 这样以来，我们就知道了左子树的前序遍历和中序遍历结果，
        // 以及右子树的前序遍历和中序遍历结果，
        // 我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。